import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    int[] dx = {0, 0, -1, 1};
    int[] dy = {1, -1, 0, 0};

    /**
     * 图片渲染
     * @param image
     * @param sr
     * @param sc
     * @param color
     * @return
     */
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int prev = image[sr][sc]; // 记录原始颜色
        // 判断边界条件
        if (prev == color) {
            return image;
        }
        Queue<int[]> queue = new LinkedList<>();
        int m = image.length;
        int n = image[0].length;
        image[sr][sc] = color;
        queue.offer(new int[]{sr, sc});
        while(!queue.isEmpty()) {
            // 取出队列元素
            int[] index = queue.poll();
            int a = index[0];
            int b = index[1];
            for(int i = 0; i < 4; i++) {
                int x = a + dx[i];
                int y = b + dy[i];
                if ((x >= 0 && x < m)
                        && (y >= 0 && y < n)
                        && (image[x][y] == prev)) {
                    image[x][y] = color;
                    queue.offer(new int[]{x, y});
                    //System.out.println("x: " + x + " y: " + y);
                }
            }
        }
        return image;
    }

    boolean[][] vis;
    public int numIslands(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int res = 0;
        vis = new boolean[m][n];
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if (grid[i][j] == '1' && vis[i][j] == false) {
                    bfs(grid, i, j, m, n);
                    res++;
                }
            }
        }
        return res;
    }
    public void bfs(char[][] grid, int sr, int sc, int m, int n) {
        if (vis[sr][sc]) {
            return;
        }
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{sr, sc});
        vis[sr][sc] = true;
        while(!queue.isEmpty()) {
            int[] tmp = queue.poll();
            int a = tmp[0];
            int b = tmp[1];
            for(int i = 0; i < 4; i++) {
                int x = a + dx[i];
                int y = b + dy[i];
                if (x >= 0 && x < m
                        && y >= 0 && y < n
                        && grid[x][y] == '1' && vis[x][y] == false) {
                    vis[x][y] = true;
                    queue.add(new int[]{x, y});
                }
            }
        }
    }

    /**
     * 岛屿的最大面积
     * @param grid
     * @return
     */
    public int maxAreaOfIsland(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int max = 0;
        vis = new boolean[m][n];
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if (grid[i][j] == 1 && !vis[i][j]) {
                    max = Math.max(max,bfs(grid, i, j, m, n));
                }
            }
        }
        return max;
    }

    public int bfs(int[][] grid, int sr, int sc, int m, int n) {
        if (grid[sr][sc] != 1 || vis[sr][sc]) {
            return 0;
        }
        Queue<int[]> queue = new LinkedList<>();
        int res = 1;
        queue.add(new int[]{sr, sc});
        vis[sr][sc] = true;
        while(!queue.isEmpty()) {
            int[] tmp = queue.poll();
            int a = tmp[0];
            int b = tmp[1];
            for(int i = 0; i < 4; i++) {
                int x = a + dx[i];
                int y = b + dy[i];
                if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !vis[x][y]) {
                    res++;
                    vis[x][y] = true;
                    queue.add(new int[]{x, y});
                }
            }
        }
        return res;
    }

    /**
     * 被围绕的区域
     * @param board
     */
    public void solve(char[][] board) {
        int m = board.length;
        int n = board[0].length;
        // 先处理边
        for(int j = 0; j < n; j++) {
            if (board[0][j] == 'O') bfs1(board, 0, j, m, n);
            if (board[m - 1][j] == 'O') bfs1(board, m - 1, j, m, n);
        }
        for(int i = 0; i < m; i++) {
            if(board[i][0] == 'O') bfs1(board, i, 0, m, n);
            if (board[i][n - 1] == 'O') bfs1(board, i, n - 1, m, n);
        }
        // 还原
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                if (board[i][j] == '.') board[i][j] = 'O';
            }
        }

    }
    public void bfs1(char[][] board, int sr, int sc, int m, int n) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{sr, sc});
        board[sr][sc] = '.';
        while(!queue.isEmpty()) {
            int[] tmp = queue.poll();
            int a = tmp[0];
            int b = tmp[1];
            for(int i = 0; i < 4; i++) {
                int x = a + dx[i];
                int y = b + dy[i];
                if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O') {
                    queue.add(new int[]{x, y});
                    board[x][y] = '.';
                }
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] grid = {{0,0,1,0,0,0,0,1,0,0,0,0,0},
                {0,0,0,0,0,0,0,1,1,1,0,0,0},
                {0,1,1,0,1,0,0,0,0,0,0,0,0},
                {0,1,0,0,1,1,0,0,1,0,1,0,0},
                {0,1,0,0,1,1,0,0,1,1,1,0,0},
                {0,0,0,0,0,0,0,0,0,0,1,0,0},
                {0,0,0,0,0,0,0,1,1,1,0,0,0}, {0,0,0,0,0,0,0,1,1,0,0,0,0}};
        solution.maxAreaOfIsland(grid);
    }
}
